//1. 环绕字符串中唯一的子字符串:
class Solution 
{
public:
    int findSubstringInWraproundString(string s) 
    {
        //思考: dp[i]表示到达i位置的时候不同子串也在base出现的个数;
        int n = s.size();
        vector<int> dp(n, 1);

        for(int i = 1; i < n; i++)
        {
            if(s[i - 1] + 1 == s[i] || (s[i - 1] == 'z' && s[i] == 'a'))
            {
                dp[i] += dp[i-1];
            }
        }

        //这里处理相同位置i的最大的dp值.
        int hash[26];
        for(int i = 0; i < n; i++)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }

        //统计每个位置的最长dp值加和;
        int ret = 0;
        for(auto& i : hash)
            ret += i;
        
        return ret;
    }
};


//2. 最长递增子序列
class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        //思路: 到达i位置为结尾时候, 最大递增子序列的长度;
        int n = nums.size();
        vector<int> dp(n, 1);//这里初始化为1代表一个元素也可以为一个子序列;

        for(int i = 1; i < n; i++)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }


        int ret = 1;
        for(auto& i : dp)
            ret = max(ret, i);
        
        return ret;
    }
};


//3. 摆动序列
class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);

        for(int i = 1; i < n; i++)
        {
            for(int j = i - 1; j >= 0; j--)
            {
                if(nums[j] < nums[i])
                {
                    f[i] = max(f[i], g[j] + 1);
                }

                if(nums[j] > nums[i])
                {
                    g[i] = max(g[i], f[j] + 1);
                }
            }
        }


        int ret = 1;
        for(int i = 0; i < n; i++)
        {
            ret = max(ret, max(f[i], g[i]));
        }

        return ret;
    }
};


//4. 在数组中找出最大值出现的次数;
int MaxlenSize(vector<int>& nums)
{
    if(nums.size() == 1) return 1;
    return 
}


